package com.排序算法;

import java.util.Random;

public class 快速排序 {
    public static void quickSort(int arr[], int low, int high) {
/*        int i = low, j = high;
        // 把数组中间的元素设置为基准数
        int pivot = a[low + (high - low) / 2];

        // 分开成两个数组
        while (i <= j) {
            //从左向右“探测”，如果左边的元素小于基准数，则去“探测”下一个元素
            while (a[i] < pivot) {
                i++;
            }
            //从右向左“探测”，如果左边的元素大于基准数，则去“探测”下一个元素
            while (a[j] > pivot) {
                j--;
            }

            // 如果左边探测结果大于基准数，右边探测结果小于基准数，那么交换这两个元素
            // 然后继续探测
            if (i <= j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        // 递归
        if (low < j)
            quickSort(a,low, j);
        if (i < high)
            quickSort(a,i, high);
    }*/


        int i = low, j = high;
        int pivot = arr[low + (high - low) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        if (low < j) {
            quickSort(arr, low, j);
        }
        if (i < high) {
            quickSort(arr, i, high);
        }

    }

    public static void main(String[] args) {
        int arrays[] = new int[100];
        int arrays1[] = new int[100];
        Random random = new Random();
        for (int i = 0; i < arrays.length; i++) {
            arrays[i] = random.nextInt(1000);
        }
        System.arraycopy(arrays, 0, arrays1, 0, arrays.length);
        quickSort(arrays, 0, arrays.length - 1);
        冒泡排序 冒泡排序 = new 冒泡排序();
        冒泡排序.bubbleSort(arrays1);
        System.out.println(" ");
        System.out.println("快速排序排序算法结果：");
        for (int i = 0; i < arrays.length; i++) {
            if (i % 10 == 0) {
                System.out.println(" ");
            }
            System.out.print(arrays[i] + " ");
        }
        System.out.println(" ");
        System.out.println("冒泡排序排序算法结果：");
        for (int i = 0; i < arrays1.length; i++) {
            if (i % 10 == 0) {
                System.out.println(" ");
            }
            System.out.print(arrays1[i] + " ");
        }
        boolean flag = true;
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] == arrays1[i]) {
                flag = flag && true;
            } else {
                flag = false;
            }
        }
        System.out.println("");
        System.out.println("排序结果是否正确:" + (flag ? "√" : "×"));
    }
}
